#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;


//堆01：最后一块石头的重量
class Solution1 {
public:
    int lastStoneWeight(vector<int>& stones) 
    {
        hp(stones);
        while(stones.size()>1)
        {
            cout<<stones.size();
            int x=top(stones);
            int y=top(stones);
            if(x!=y)
            {
                int tmp=x>y?(x-y):(y-x);
                push(stones,tmp);
            }
        }
        if(stones.empty())  return 0;
        else return stones[0];
    }

    void hp(vector<int>& stones)
    {
        int n=stones.size();
        for(int i=n/2-1;i>=0;i--)
        {
            Adjustdown(stones,i,n);
        }
    }

    void Adjustdown(vector<int>& stones,int parent,int n)
    {
        int leftchild=2*parent+1;
        int rightchild=2*parent+2;
        while(leftchild<n)
        {
            int max=0;
            if(rightchild>=n)   max=leftchild;
            else
            {
                max=stones[leftchild]>=stones[rightchild]?leftchild:rightchild;
            }
            if(stones[parent]>stones[max])  break;
            else
            {
                swap(stones[parent],stones[max]);
                parent=max;
                leftchild=2*parent+1;
                rightchild=2*parent+2;
            } 
        }
    }

    void Adjustup(vector<int>& stones,int child)
    {
        int parent=(child-1)/2;
        while(child>0)
        {
            if(stones[child]>stones[parent])
            {
                swap(stones[child],stones[parent]);
                child=parent;
                parent=(child-1)/2;
            }
            else break;
        }
    }

    int top(vector<int>& stones)
    {
        int n=stones.size();
        swap(stones[0],stones[n-1]);
        int tmp=stones[n-1];
        stones.pop_back();
        Adjustdown(stones,0,n-1);
        return tmp;
    }

    void push(vector<int>& stones,int nums)
    {
        stones.push_back(nums);
        Adjustup(stones,stones.size()-1);
    }
};

//堆02：数据流中的第K大元素
class KthLargest {
public:
    priority_queue<int,vector<int>,greater<int>> hp;
    //int size=0;
    int _k;
    KthLargest(int k, vector<int>& nums)
    :_k(k)
    {
        for(auto &it:nums)
        {
            hp.push(it);
            if(hp.size()>_k) hp.pop();
        }   
    }
    
    int add(int val) 
    {
        hp.push(val);
        if(hp.size()>_k) hp.pop();
        return hp.top();      
    }

private:

};


//堆03:前K个高频单词
class Solution3 {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> cnt;
        for (auto& word : words) {
            ++cnt[word];
        }
        vector<string> rec;
        for (auto& [key, value] : cnt) {
            rec.emplace_back(key);
        }
        sort(rec.begin(), rec.end(), [&](const string& a, const string& b) -> bool {
            return cnt[a] == cnt[b] ? a < b : cnt[a] > cnt[b];
        });
        rec.erase(rec.begin() + k, rec.end());
        return rec;
    }
};





void test2()
{
    vector<int> nums{4,5,8,2};
    KthLargest SL(3,nums);
    SL.add(3);
    SL.add(5);
    SL.add(10);
    SL.add(9);
    SL.add(4);
}



void test1()
{
    vector<int> nums={3,7,2};
    //vector<int> nums={2,7,4,1,8,1};
    Solution1 SL;
    SL.lastStoneWeight(nums);
}


int main()
{
    test2();
    return 0;
}